"""
LeetCode 热题

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""
"""
from collections import deque, Counter

class Solution(object):
    def minWindow(self, s, t):
        """
        返回字符串 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。

        参数:
        s: str，源字符串。
        t: str，目标字符串。

        返回:
        str，s 中涵盖 t 所有字符的最小子串；如果不存在这样的子串，则返回空字符串 ""。
        """
        if not s or not t:
            return ""

        # 记录 t 中每个字符的出现次数
        t_count = Counter(t)
        # 记录当前窗口内字符的出现次数
        window_count = Counter()
        # 用于存储当前窗口内的字符索引
        window = deque()
        # 记录结果子串的起始和结束索引
        result = (float('inf'), float('-inf'))
        # 当前窗口内满足条件的字符数
        formed = 0

        for i, char in enumerate(s):
            # 将当前字符加入窗口
            window_count[char] += 1
            # 如果当前字符在 t 中且数量达到要求，增加 formed
            if char in t_count and window_count[char] == t_count[char]:
                formed += 1

            # 移除窗口左边的字符，直到窗口不再满足条件
            while formed == len(t_count) and window:
                # 更新结果子串
                if i - window[0] + 1 < result[1] - result[0] + 1:
                    result = (window[0], i)

                # 从窗口中移除左边的字符
                left_char = s[window.popleft()]
                window_count[left_char] -= 1
                # 如果移除的字符在 t 中且数量不足，减少 formed
                if left_char in t_count and window_count[left_char] < t_count[left_char]:
                    formed -= 1

            # 将当前字符的索引加入窗口
            window.append(i)

        # 如果没有找到满足条件的子串，返回空字符串
        if result[0] == float('inf'):
            return ""
        else:
            # 返回结果子串
            return s[result[0]:result[1] + 1]

if __name__ == '__main__':
    a = Solution()
    print(a.minWindow("a", "a"))  # 输出应为 "a"